Methods of mechanically or electromechanically sorting data into ascending or descending sequence dates back to the Herman Hollerith designed punch card, which was developed in the late nineteenth century. Hollerith was presented with the problem that the U.S. census data gathered in 1880 was never tabulated due to the inability of manually processing such an immense amount of data. Hollerith, a Census Bureau employee, proceeded to invent machines to tabulate and sort the data for the census of 1890, 1900 and the decades to follow. Improved versions of the Hollerith design continued to be used for the sorting of large amounts of data for many years to follow.
The advent of the modern electronic digital computer has facilitated the creation of computer based sorting methods that have replaced the electromechanical Hollerith-type machines. In the Hollerith-type devices, the punched card sorting techniques were predicated upon sorting one card column at a time, rather than all the punched columns which make up the data word. Through numerous iterations the ranked order of encoded data punched on the cards was determined. The digital computer has been devised with the ability to sort data in an internal memory. This permits digital computers to compare data words rather than just a single data column on each pass. The digital computer is far faster than the Hollerith-type sorting machines since not only can the whole word be comprehended at one time but the electronic computer operates at a far faster speed because it is purely electronic and does not rely on electromechanical handling and sorting devices.
In recent years, various innovative sorting techniques have been devised in an effort to increase the speed of the sorting process. Most of these techniques rely upon some type of iterative process in which the unsorted data is compared, categorized and handled through a varying number of iterations before the ranked order results in a sorted tabulation. For a large table of unsorted data, even modern electronic computers take considerable time to complete this iteration process. Some estimate that over twenty-five percent of the running time of modern computers is spent on the sorting of unsorted data.
It should also be noted that current data sorting techniques are slowed by increased data table size. The increased number of data words and consequent larger data tables to be sorted result in an increase in computer time required per item per table. This time increase per item varies with the method of sorting used but with all current methods, time increases with table size.
In view of the above, there is a need for a method of sorting data by a computer at higher speeds than is currently possible.
It is therefore an object of this invention to provide a high-speed data sorting method that will greatly reduce the amount of time digital computers require to sort large volumes of data.
It is a further object of this invention to greatly reduce the number of time consuming iterations required to completely process an unsorted data table.
It is yet another object of this invention to provide a data sorting method that reduces the sorting time increase that is generally brought about by enlarging data tables.
It is an advantage of this invention that the improvement in sorting speed greatly increases as table size increases since the time used by this technique increases linearly with table size rather than at some higher order.